# 路径总和III：https://leetcode-cn.com/problems/path-sum-iii/submissions/
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        """
            虽然这道题不再是从根节点到叶子结点，但是 是 从根节点，到叶子结点方向的。
            这道题是比较难想的，按照视频讲解的思路， 这道题需要充分理解运用递归。
            
            核心： 既要在 “递” 时完成一些事情， 又要在 “归” 时，完成一些事情。

            # 1. 注意： 在 “递” 时需要完成找到所有的路径和
            如例子中， 遍历到根节点 
            10： 有一条路径， 路径和为：10
            5 ： 两条路径 [15, 5]  上一节点加这一节点路径和， 及当前节点路径和
            3 ： 三条路径 [18, 8, 3] 依次是： 10 -> 5 -> 3,  5 -> 3, 3 三条路径的和
            3  : [21, 11, 6, 3] 
            有些类似前缀和。

            # 2. 注意： 在 “归” 时 需要统计 满足条件的路径个数
            可以看出数 深度遍历使用 前序遍历，根左右。 那么归时， 也就是回溯时， 就要将左右子节点的 符合条件的路径数，返回给父节点。

            时间复杂度为 O(nlogn), 遍历所有节点 O(n), 每个节点需要计算 路径和 还有 cnt , 所以是logn , 大致等于树的深度
        """

        def dfs(node, pathSum):
            if not node: return 0

            # 注意： 不可以直接改变父亲节点的 pathSum, 要复制一份。因为都是数值，不可变对象，所以浅拷贝即可
            curPathSum = pathSum.copy()
            for i in range(len(curPathSum)):
                curPathSum[i] += node.val
            curPathSum.append(node.val)

            cntLeft = dfs(node.left, curPathSum)    
            cntRight = dfs(node.right, curPathSum)
            
            # 这一块求和，可以放到上面 求 curPathSum 一起计算
            cnt = 0
            for num in curPathSum:
                if num == targetSum:
                    cnt += 1

            return cntLeft + cntRight + cnt

        return dfs(root, [])


# 请看当前目录下的， 路径总和III部分逻辑.py,查看前缀和求法
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        """
            使用前序遍历 加 前缀和, 遍历的时候，动态维护根节点，到当前节点的前缀和。判断当前节点是否有满足的
            这里使用的还是纯 前缀和的逻辑， 显示的定义一个 前缀和数组
        """
        # 1. 递归求出所有的 根节点，到叶子结点的路径
        cnt = 0
        def dfs(node, prefix, map):
            nonlocal cnt
            if not node: return 
            # 1. 添加当前元素到前缀和, 并判断是否有满足的 
            prefix.append(prefix[-1] + node.val)
            cnt += map.get(prefix[-1] - targetSum, 0)
            map[prefix[-1]] = map.get(prefix[-1], 0) + 1

            # 2. 遍历左右子树
            dfs(node.left, prefix, map)     
            dfs(node.right, prefix, map)

            # 3. 回溯时，去掉增加的当前节点的信息
            map[prefix[-1]] -= 1
            # if map.get(prefix[-1]) == 0: del map[prefix[-1]]
            prefix.pop()
        
        dfs(root, [0], {0: 1})

        return cnt


# 观察程序执行 可以发现，没必要维护一个 前缀和数组， 因为当前执行的函数， 只使用调用者的当前的前缀和
# 所以，这个前缀和数组，完全可以用一个变量来代替
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        """
            利用一个变量代替前缀和数组， 最后的回溯部分，不需要再进行回溯前缀和了，只需要把当前的 map 回溯，
            将当前添加的元素修改去掉即可
        """
        # 1. 递归求出所有的 根节点，到叶子结点的路径
        cnt = 0
        def dfs(node, prefix, map):
            nonlocal cnt
            if not node: return 
            # 1. 添加当前元素到前缀和, 并判断是否有满足的 
            prefix =  prefix + node.val
            cnt += map.get(prefix - targetSum, 0)
            map[prefix] = map.get(prefix, 0) + 1

            # 2. 遍历左右子树
            dfs(node.left, prefix, map)     
            dfs(node.right, prefix, map)

            # 3. 回溯时，去掉增加的当前节点的信息
            map[prefix] -= 1
        
        dfs(root, 0, {0: 1})

        return cnt


        